CSE 311: Foundations of Computing I

CSE 311: Homework 6 Part 1

Due: Thursday, May 28th by 6:00 PM

Instructions

Complete the problems on the following pages.

You are required to submit your own solutions. You are allowed to discuss the homework with other students. However, you must complete the problems in Grin on your own. Moreover, you must be able to explain your solution at any time. We reserve ourselves the right to ask you to explain your work at any time in the course of this class.

You have a total of three late days during the quarter, but you can only use one late day on any one homework, giving an additional day on both parts. Please plan ahead.

Submit your solution at http://grin.cs.washington.edu

  • Each part of each task is listed as its own problem.

  • You have unlimited attempts on each part.

  • All completed parts get full credit and uncompleted parts get no credit.

Task 1 – Final Study Mission

Use the algorithm from lecture to convert each of the following NFAs to DFAs. Label each DFA state with the set of NFA states it represents in the powerset construction.

Important: Grin does not validate whether your state labels are correct. But do not skip them – correct state labels on DFAs will be required on quiz/exam with NFA-DFA conversion problems.

  1. The NFA below, which accepts any binary string containing “00” as a substring:

    NFA that starts at state 0. From here, an arrow to loop itself with 0,1 and an arrow to the next state with 0. State 1 loops itself with 1 and can go to state 3 with 0. State 3 goes back to State 1 with 1, and goes to State 4 with the empty string. State 2 goes to State 3 with 1, loops itself wih 0 and goes to State 4 with the empty string or 1. State 4 is the accepting state, arriving from States 2 and 3, and can go to State 2 with the empty string. There is a cycle between states 1 and 3, and a triangular cycle with States 2, 3, and 4, where 2 and 4 have a separate cycle as well.

  2. The NFA below, which accepts strings starting with “10”or ending in “01":

    NFA that starts at state 0. From here there are two paths. Visually, this is the top path, which goes to state 1 with the empty string, state 2 with 1, and state 3 with 0. State 3 loops itself with 0,1 and is an accepting state. The bottom path goes to state 4 with the empty string, where state 4 loops itself with 0,1. State 4 goes to state 5 with 0, and goes to the accepting state 6 with 1.

Task 2 – A Whole New Small Game

Use the algorithm from lecture to minimize the each of the following DFAs.

For each step of the algorithm, write down the groups of states, which group was split in that step and the reason for splitting that group. At the end, write down the minimized DFA, with each state named by the set of states of the original machine that it represents (e.g., “{B,C}\{B,C\}”).

Important: Grin does not validate whether your DFA is correctly minimized or whether your state labels are correct. You do not need to separately submit your algorithm steps or state labels for this homework. But do not skip these steps — the full algorithm run and correct state labels will be required on quiz/exam with DFA minimization problems.

  1. The following machine:

    The non-minimal DFA starts with state 0. State 0 can go to the accepting state 1 with 1, or state 4 with 0. State 4 goes to state 0 with 0 (a cycle between states 0 and 4) and to state 1 with 1. State 1 goes to state 4 with 1 (a cycle between states 1 and 4) and to state 5 with 0. State 5 goes to state 1 with 0 (a cycle between states 1 and 5) and goes to state 3 with 1. State 3 goes to state 4 with 1 and state 2 with 0. State 2 is an accepting state and goes to state 5 with 0 and state 0 with 1. There is a triangle path between states 2, 5, and 3.

  2. The following machine:

    The non-minimal DFA starts with state 0. State 0 goes to state 1 with 0 and state 4 with 1. State 1 is an accepting state that goes to state 0 with 0 (a cycle between states 0 and 1) and goes to state 6 with 1. State 6 goes to the accepting state 2 with 0 and the accepting state 4 with 1. State 2 goes to state 0 with 0 and state 6 with 1 (a cycle between states 2 and 6). State 4 goes to state 1 with 1, and to state 5 with 0. State 5 goes to state 2 with 0 and to state 3 with 1. State 3 goes to state 5 with 1 (a cycle between states 3 and 5) and loops itself with 0. As a summary, we start at state 0 and accept states 1, 2, and 4.